package 链表和树.链表.digui;
//Java：合并两个有序链表
public class MergeTwoSortedLists{
    public static void main(String[] args) {
        Solution solution = new MergeTwoSortedLists().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
//    public class ListNode {
//        int val;
//        ListNode next;
//        ListNode() {}
//        ListNode(int val) { this.val = val; }
//        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
//    }
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //本题
        //终止条件：当两个链表都为空时，表示我们对链表已合并完成。
        //如何递归：我们判断 l1 和 l2 头结点哪个更小，然后较小结点的 next 指针指向其余结点的合并结果。（调用递归）
        //递归函数必须要有终止条件，否则会出错；
        //递归函数先不断调用自身，直到遇到终止条件后进行回溯，最终返回答案。
        if(list1 == null){
            return list2;
        }else if(list2 == null){
            return list1;
        } else if (list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else  {
            list2.next = mergeTwoLists(list2.next,list1);
            return list2;//最终返回合并后的链表头节点
        }


        //总结
        //常见的递归模型，本质就分两种：
        //
        //一种是阶乘公式，f(n) = n * f(n-1)；
        //另一种是斐波那契公式，f(n) = f(n - 1) + f(n - 2)。一般情况下，还需要处理本层的任务，因此，扩展公式是：f(n) = n + f(n - 1) + f(n - 2)。
        //把要解决的问题，抽象为数学模型描述，如果可以用以上两种公式模型套进去，就可以用递归。
        //比如这道题，本质就是阶乘的模型，当前问题是 f(n)，从 list1 和 list2 中找出较小的那个，作为 n，剩下的所有节点构成的问题作为 f(n-1)。最终，f(n) = 找出 n + 解决 f(n-1)。
    }
        public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
            ListNode dummy = new ListNode(); // 用哨兵节点简化代码逻辑
            ListNode cur = dummy; // cur 指向新链表的末尾
            while (list1 != null && list2 != null) {
                if (list1.val < list2.val) {
                    cur.next = list1; // 把 list1 加到新链表中
                    list1 = list1.next;
                } else { // 注：相等的情况加哪个节点都是可以的
                    cur.next = list2; // 把 list2 加到新链表中
                    list2 = list2.next;
                }
                cur = cur.next;
            }
            cur.next = list1 != null ? list1 : list2; // 拼接剩余链表
            return dummy.next;
        }
}
//leetcode submit region end(Prohibit modification and deletion)

}